The present invention relates generally to data processing in a device having a plurality of memory modules, which are accessed in parallel in order to retrieve and store data elements in the memory modules, and, more particularly, to a power-of-two stride access, and a dynamic storage scheme for such a device.
In hardware architectures containing parallel processing resources, several operands from the memory need to be transferred simultaneously for matching the processing power with the memory bandwidth. Multiple operand access can be realized by allocating an independent memory module for each operand access. With this approach, however, problems arise from the fact that the parallel data accesses are not always linear. That introduces access conflicts in that the data operands to be accessed are in the same memory modules and, therefore, they cannot be accessed simultaneously.
In digital signal processing (DSP), data elements are often accessed by taking every Kth element from the data array of N elements, wherein N=2n, K=2k with n=1, 2, . . . and k=0, 1, 2, . . . , nxe2x88x921. In particular, every Kth element is taken but when the access exceeds Nxe2x88x921, the access pattern wraps back to the beginning. The elements are accessed in the order as shown below, with p being the new address and i being the linear ordering index:
p=mod(Ki,N)+└Ki/N┘, i=0, 1, . . . , Nxe2x88x921
where └z┘ denotes the floor function of z, and is the greatest integer less than or equal to z; mod is a modulus operation. With such access ordering, an N-point array (x1, X1, X2, . . . XNxe2x88x921) will be accessed as (x0, XK, X2K, . . . , XNxe2x88x92K, X1, XK+1, X2K+1, . . . ). Such an access pattern is related to stride by K permutation. Here K is a number defined by a power of two, and thus the access is referred to as a power-of-two stride access. Such interconnection topologies are present, for example, in discrete trigonometric transforms and trellis coding. A mapping method to enhance parallel power-of-two stride access is disclosed in Melton et al. (EP 0 313 788 B1). When an N-element data block has N memory locations distributed over Q memory modules, Q parallel accesses of every Kth data element can be carried out such that N=2n, Q=2q, K=2k with n=1, 2, . . . , q=1, 2, . . . , nxe2x88x921 and k=0, 1, 2, . . . , nxe2x88x921.
In the past, access conflicts were avoided by using a technique called double buffering, where 2N memory locations are allocated for an N-point data array. With double buffering, while the data at one location is being written, the data at another location is read. This approach has been used in Viterbi-decoding in some DSP processors. The major drawback for this approach is that it increases the size of memory and increases the latency as well. Memory accesses can also be hard-coded into the software code. This method increases the code size. Alternatively, look-up tables can be used. However, look-up tables also increase the memory consumption and the number of memory accesses. Furthermore, multi-port memories can be used, but they are expensive in terms of area.
Specialized address generation units have been proposed, but they support only one specific stride-byxe2x88x922k (a single access pattern) along with a stride-byxe2x88x921, which is the linear access, or they are limited to certain data array sizes. Harper (U.S. Pat. No. 4,918,600) discloses a method of stride access wherein only two strides 1 and 2k are supported at a time. However, Harper does not support stride-by-1 and stride-by-N/2 when more that 2 memories are used, i.e., 4, 8, etc. In such a case, we need to access elements indices (0, N/2, 1, N/2+1, 2, . . . ). Especially parallel access of N/2 and 1 presents the conflict. The specialized address generation units may also support a certain number of parallel memories, as disclosed in Cohen (IEEE Trans Acoustics, Speech, and Signal Processing, December 1976, pp.577-579).
Currently there are also parallel access schemes, which require an odd number of memory modules, and the number of memory modules being greater than the number of operands accessed simultaneously, as disclosed in D. T. Harper, xe2x80x9cBlock, multistride vector, and FFT accesses in parallel memory systems,xe2x80x9d (IEEE Trans. Parallel and Distributed Systems, vol. 2, no. 1, pp. 43-51, Jan. 1991). With these schemes, the memory consumption is also high and the memory is fragmented.
Thus, it is advantageous and desirable to provide a method and device for efficiently generating the addresses for Q parallel memory accesses according to stride permutation.
It is a primary object of the invention to provide a method of conflict-free access to parallel memory modules in a data processing device.
It is another object of the invention to provide an apparatus and system for mapping address locations to physical memory locations in parallel memory modules for conflict-free access for several strides.
These objects can be achieved by pre-selecting a storage scheme for each data block based on the number of elements in that data block and number of memory modules.
Thus, according to the first aspect of the present invention, there is provided a method of accessing data elements of an N-element data block on N memory locations distributed over Q memory modules via Q parallel accesses, wherein
said N memory locations are addressable in an n-bit index address, and
said Q memory modules are addressable in a q-bit module address and an (nxe2x88x92q) bit row address. The method is characterized by:
selecting (nxe2x88x92q) bits from the index address for providing the row address;
grouping the index address into a plurality of fields comprising a number of first fields, wherein each of the first fields contains q bits; and
performing a logical function operation on bits obtained from corresponding positions in said plurality of fields for providing the module address for accessing the data element in one of said Q memory modules.
According to the present invention, said plurality of fields may comprise a second field, wherein the second field contains e bits, e being a positive integer smaller than q, and e depends on the relationship between n and q.
Preferably, the method is further characterized by performing a rotation operation on one of said plurality of fields for providing a third field, wherein said logical function is also performed on the third field in addition to said plurality of fields.
Preferably, the method is further characterized by concatenating (qxe2x88x92e) zeros to the second field.
According to the present invention, the method is further characterized by performing a rotation operation on one of said plurality of fields for providing a third field, wherein the one field on which the rotation operation is performed contains the least significant bits, and wherein said logical function is also performed on the third field in addition to said plurality of fields.
Preferably, said logical function is a bitwise exclusive-OR operation.
According to the present invention the n-bit index address can be arranged into an arbitrary order. In addition, the q-bit memory module address can also be reordered into arbitrary order.
According to the second aspect of the present invention, there is provided an apparatus for accessing a data element of an N-element data block on N memory locations distributed over Q memory modules via Q parallel accesses, wherein
said N memory locations are addressable in an n-bit index address, and
said Q memory modules are addressable in a q-bit module address and an (nxe2x88x92q) bit row address. The apparatus is characterized by:
means (12), operatively connected to the index address, for selecting (nxe2x88x92q) bits from the index address for providing the row address; and
means (40), operatively connected to the index address, for grouping the index address into a plurality of fields comprising a number of first fields, and for performing a logical function operation on bits obtained from corresponding positions in said plurality of fields for providing the module address for accessing the data elements in said Q memory modules, wherein each of the first fields contains q bits.
According to the present invention, said plurality of fields may further comprise a second field, wherein the second field contains e bits, e being a positive integer smaller than q, and e depends on the relationship between n and q; and the apparatus further comprises means (31), operatively connected to the second field, for concatenating (qxe2x88x92e) zeros to the second field prior to the performance of the logical function.
Advantageously, the apparatus is further characterized by means (30), operatively connected to one of said plurality of fields, for performing a rotation operation on said one of said plurality of fields for providing a third field, wherein said logical function is also performed on the third field in addition to said plurality of fields.
Preferably, the grouping and performing means (40) comprises a plurality of exclusive-OR devices.
According to the third aspect of the present invention, there is provided a data processing system (100) comprising a memory unit (120) for storing data elements and a data processing module (140), operatively connected to the memory unit for accessing the data elements, wherein the memory unit comprises an N-element data block in N memory locations addressable in an n-bit index address (20). The system is characterized in that the N-element data block on N memory locations is distributed over Q memory modules (1200, . . . , 120Qxe2x88x921), wherein the Q memory modules are addressable in a q-bit module address (M) and an (nxe2x88x92q) bit row address (R);
the data processing module comprises Q data processors (1420, . . . , 142Qxe2x88x921), adapted to accessing the Q memory modules via Q parallel accesses; said system further characterized by
an address generator (100), operatively connected to the memory unit, for providing access to the data elements in the memory unit, wherein the address generator comprises:
a first address generator (12), operatively connected to the index address (20), for providing the row address (R); and
a second address generator (40), operatively connected to the index address (20), for providing the module address (M), and
an interconnector means (130, 132), operatively connected to the address generator (100), the memory unit 120 and the data processor module 140, for allowing the Q data processors to access the data elements in the Q memory modules, wherein
the row address provided by the first address generator (20) is selected from (nxe2x88x92q) bits of the index address, and
the module address provided by the second address generator is obtained by:
grouping the index address (20) into a plurality of fields comprising a number of first fields, each first field containing q bits; and
performing a logical function operation on bits obtained from corresponding position in said plurality of fields.